package TreeTest;

import sun.reflect.generics.tree.Tree;

import java.util.*;

public class Main1 {
    static class Node{
        int val ;
        ArrayList<Integer> list;

        public Node(int val, ArrayList<Integer> list) {
            this.val = val;
            this.list = list;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ArrayList<Integer> getList() {
            return list;
        }

        public void setList(ArrayList<Integer> list) {
            this.list = list;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<Integer,ArrayList<Integer>> nodeHashMap = new HashMap<>();
        int N = sc.nextInt();   //表示城市数
        int[][] rea = new int[N-1][2];
        for(int i = 0; i < N-2; i++){
            for(int j = 0; j < 2; j++){
                
            }

        }
        /*5,[[2,4],[1,4],[0,3],[0,3]]*/

        /*int[][] arr = new int[7][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 2;
        arr[1][1] = 1;
        arr[2][0] = 5;
        arr[2][1] = 2;
        arr[3][0] = 6;
        arr[3][1] = 5;
        arr[4][0] = 7;
        arr[4][1] = 5;
        arr[5][0] = 3;
        arr[5][1] = 1;
        arr[6][0] = 4;
        arr[6][1] = 1;


        int[][] res = invert_tree(arr);
        for (int a=0;a<res.length;a++){
            System.out.print(res[a][0]);
            System.out.println(res[a][1]);
        }
*/

    }

    public static int[][] invert_tree (int[][] node_data_list) {
        // write code here
        /*  [[1,0],[2,1],[5,2],[6,5],[7,5],[3,1],[4,1]]*/
        TreeMap<Integer,ArrayList<Integer>> nodes = new TreeMap<>();
        for (int a = 0;a<node_data_list.length;a++){
            int a2 = node_data_list[a][0];
            int a1 = node_data_list[a][1];
            if (nodes.containsKey(a1)){
                nodes.get(a1).add(a2);
            }else {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(a2);
                nodes.put(a1,arr);
            }
        }
        int[][] res = new int[node_data_list.length][2];
        Set<Integer> set  = nodes.keySet();
        Iterator<Integer> it = set.iterator();
        int R= 0;
        while (it.hasNext()){
            int key = it.next();
            ArrayList<Integer> arrayList = nodes.get(key);
            if (!arrayList.isEmpty()){
                for (int a = arrayList.size()-1;a>=0;a--){
                    res[R][0]=arrayList.get(a);
                    res[R][1]=key;
                    R++;
                }
            }
        }
        return res;
    }



    public static int determine_virus_type (int size, int[][] swap_indexes) {
        // write code here
        int[] arr = new int[size];
        for (int a=0;a<arr.length;a++){
            arr[a] = size-a;
        }
        //初始化数组完毕
        int res1 = 0;
        for (int b = 0;b<swap_indexes.length;b++){
            int a1= swap_indexes[b][0];
            int a2= swap_indexes[b][1];
            res1+=(arr[a1] - arr[a2]);
            swap(arr,a1,a2);
        }

        //交换完毕  查看前比后小
        int res = 0;
        for (int x = 0;x<arr.length;x++){
            int p = arr[x];
            for (int y = x;y<arr.length;y++){
                if (p<arr[y]){
                    res++;
                }
            }
        }
      return res1%2 == 1 ? 1 : 2;
    }

    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }




    //反转的本质 如果一个节点有两个及以上的子节点  则将子节点顺序互换
    /*public int[][] invert_tree (int[][] node_data_list) {
        // write code here
        int[][] res= new int[node_data_list.length][2];
        if (node_data_list.length == 0){
            return res;
        }


    }
*/


    /*public static int getBuyNum(int restMoney, ArrayList<String> restList,int num){
        return 1;
    }*/

    public static int getMaxValue(int[] weight,int[] value,int index,int rest){
        if (rest<=0){
            return 0;
        }
        if (index == weight.length){
            return 0;
        }
        int p1=getMaxValue(weight, value, index+1, rest);
        int p2=Integer.MIN_VALUE;
        if (rest>=weight[index]){
            p2=value[index]+getMaxValue(weight, value, index+1, rest-weight[index]);
        }
        return Math.max(p1,p2);
    }
}
